/*
 * KnightCruise.cpp
 *
 *  Copyright   : Copyright © 2011 Binda&Aeolus; All Rights Reserved
 *  Created on: 2011-4-14
 *  Author      :洪春晓
 */
#include <iomanip>
#include<iostream>
#include <fstream>
using namespace std;

const int X = 0;
const int Y = 1;
const int DIRECTIONNUM = 8;
typedef struct DRnum
{
	int id;
	int value;
}DRnum;//用来记录一个方向接下去可走的路径数

class KnightCruise
{
	private:
		static const int N = 8;//棋盘大小
		static const int HasWalk = 1;//已走过
		static const int UnWalk = 0;//未走过

		int move[DIRECTIONNUM+1][2];//骑士行走的路线
		int chessboard[N+1][N+1];
		bool possible;      //是否摆放成功

		bool canWork(int x,int y)//可以走到x,y在位置
		{
			return x>=1 && x<=N && y>=1 && y<=N;
		}
		void print_result()
		{
			for (int i = 1; i <= N; i++)
			{
				for (int j = 1; j <= N; j++)
					cout << setw(4) << chessboard[i][j];
				cout << endl;
			}
		}
		void rank(DRnum * drNum,int x,int y)
		{
			for(int i=1; i<=DIRECTIONNUM;i++)
			{
				int tx = move[i][X] + x;
				int ty = move[i][Y] +y;
				int nx,ny;
				drNum[i].id = i;
				drNum[i].value = 0;
				if(canWork(tx,ty)==true  && chessboard[tx][ty]==UnWalk)
				{
					for(int j=1;j<=DIRECTIONNUM;j++)
					{
						nx = tx+move[j][X];
						ny = ty+move[j][Y];
						drNum[i].value += ( canWork(nx,ny) && (chessboard[nx][ny]==UnWalk));
					}
				}

			}
			for(int i=1; i<=DIRECTIONNUM; i++)
			{
				for(int j=i+1; j<=DIRECTIONNUM; j++)
				{
					if(drNum[j].value < drNum[i].value)
					{
						int tid = drNum[j].id;
						int tvalue = drNum[j].value;

						drNum[j].id = drNum[i].id;
						drNum[j].value = drNum[i].value;

						drNum[i].id = tid;
						drNum[i].value = tvalue;
					}
				}
			}
		}
		void recursive(int x,int y,int k)//递归方法
		{
			if(k > N*N)
			{
				possible = true;
				print_result();
			}
			int direction = 0;
			int nextX,nextY;


			DRnum drNum[DIRECTIONNUM+1];
			rank(drNum,x,y);

			while(direction <= DIRECTIONNUM && !possible)
			{
				direction++;
				nextX = move[drNum[direction].id][X] + x;
				nextY = move[drNum[direction].id][Y] +y;
				if( canWork(nextX,nextY)==true  && chessboard[nextX][nextY]==UnWalk)
				{
					chessboard[nextX][nextY] = k;
					if(k <= N*N)
					{
						recursive(nextX,nextY,k+1);
						if(!possible)
							chessboard[nextX][nextY] = UnWalk;
					}
				}
			}
		}
public:
//		bool iterative(int x,int y,int k)
//		{
//			possible = false;
//			chessboard[x][y] = 1;
//			int nextX,nextY;
//			int direction = 0;
//			while(k>1 && !possible)
//			{
//				if(k>60)cout<<k;
//				bool hasRoute = false;
//				for(direction = 1; direction <= DIRECTIONNUM; direction++ )
//				{
//					nextX = move[direction][X] + x;
//					nextY = move[direction][Y] +y;
//					if( canWork(nextX,nextY)==true  && chessboard[nextX][nextY]==UnWalk)
//					{
//						chessboard[nextX][nextY] = k;
//						if(k < N*N)
//						{
//							x = nextX;
//							y = nextY;
//							k++;
//							hasRoute = true;
//							break;
//						}
//						else
//						{
//							possible = true;
//							print_result();
//						}
//					}
//				}
//				if(!hasRoute)
//				{
//					chessboard[nextX][nextY] = UnWalk;
//					nextX = x;
//					nextY = y;
//					k--;
//				}
//			}
//			return possible;
//		}
	public:
		KnightCruise()
		{
			move[1][X] = 2; move[1][Y] = 1;
			move[2][X] = 1; move[2][Y] = 2;
			move[3][X] = -1; move[3][Y] = 2;
			move[4][X] = -2; move[4][Y] = 1;
			move[5][X] = -2; move[5][Y] = -1;
			move[6][X] = -1; move[6][Y] = -2;
			move[7][X] = 1; move[7][Y] = -2;
			move[8][X] = 2; move[8][Y] = -1;
			for(int i=1; i<= N; i++)
				for(int j=1; j <= N; j++)
					chessboard[i][j] = UnWalk;
			possible = false;
		}
		bool startCruise(int x,int y)
		{
			possible = false;
			chessboard[x][y] = 1;
			recursive(x,y,2);
			return possible;
		}
		void  outputRoute()
		{
			ofstream output("output.txt");
			for (int i = 1; i <= N; i++)
			{
				for (int j = 1; j <= N; j++)
					output << setw(4) << chessboard[i][j];
				output << endl;
			}
			output.close();
		}

		~KnightCruise(){}
};

